1. Field of the Invention
The invention relates generally to the field of computer algorithms and more particularly to a system and method for managing concurrent operations on linked lists.
2. Description of the Related Art
A linked list is a collection of elements, such as data elements, that are accessed in an explicitly ordered fashion. Common list access operations include a write or push operation which adds an element onto the list, and a read or pop operation which removes an element from the list.
Such list operations take a discrete interval of time to complete and often include more than one sequential step. With concurrent, a synchronous list operations taking place, a new list operation may be executed while the sequential steps of a currently-executing list operation are in progress. To avoid such a possibility and the consequent list inconsistencies and errors, prior art list management systems and methods have required that the list be locked for the duration of the list operation, whether pushing an element onto the list or popping an element from the list.
In the systems and methods of the prior art, consistency is improved at the expense of system performance. For example, new list operations are prevented from executing while the list is locked thereby reducing the throughput of the entire system.
What is needed then is a system and method for managing concurrent operations on linked lists that improves system performance. Such a system and method preferably increases system throughput by eliminating the need to lock the list under certain conditions.
A method for pushing a list element onto a linked list without locking the linked list is disclosed. The linked list includes a head element having a pointer to a first list element. The method includes the steps of (a) reading the pointer, (b) writing the pointer to a list element address field, and (c) atomically comparing the pointer written to the list element address field with the pointer to the first list element and exchanging an address of the list element for the pointer if the values compared are equal, else repeating steps (a) through (c).
An alternative embodiment of the invention includes a pop operation which polls a pop lock and takes ownership of the pop lock before popping an element from the linked list. This embodiment is preferably employed in a first condition in which the frequency of push operations dominates the frequency of pop operations and the likelihood of synchronous operations is high.
Yet another embodiment of the invention includes a method for popping a list element from a linked list, the list element including a next list element address and a list element counter. The linked list includes a head element having a pointer to the list element and a head counter equal to the list element counter, the next list element address and list element counter being stored in contiguous memory, and the pointer and head counter being stored in contiguous memory. The method includes (a) reading the pointer and head counter, (b) writing the pointer and head counter to a temporary head, (c) reading the next list element address and the list element counter from the list element, (d) incrementing the list element counter, (e) atomically comparing the pointer and head counter with the pointer and head counter written to the temporary head and exchanging the next list element address and the list element counter for the pointer and head counter if the values compared are equal, else repeating steps (a) through (e), and (f) decrementing the head counter.
This embodiment is preferably employed in a second condition in which the frequency of pop operations dominates the frequency of push operations and the likelihood of synchronous operations is low. A push operation in this embodiment operate in similar fashion to the push operation described above.
The invention includes a method by which an preferred method of pushing and popping list elements to the linked list is selected based upon the frequency of pop operations relative to push operations and the likelihood of synchronous operations.